package com.person.leetcode.editor.cn;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 23.合并K个升序链表
 * 2022-05-20 16:50:32
 **/
public class Sequence_0023_MergeKSortedLists {
    public static void main(String[] args) {
        Solution solution = new Sequence_0023_MergeKSortedLists().new Solution();

    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     */
//    public class ListNode {
//        int val;
//        ListNode next;
//
//        ListNode() {
//        }
//
//        ListNode(int val) {
//            this.val = val;
//        }
//
//        ListNode(int val, ListNode next) {
//            this.val = val;
//            this.next = next;
//        }
//    }

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
//            return MyergeKLists(lists);
            return QueueErgeKLists(lists);
        }
        //每个节点的最小值插入需返回的末尾  220 ms,43.6 MB
        public ListNode MyergeKLists(ListNode[] lists) {
            ListNode tail = null;
            ListNode ans = tail;
            while (true) {
                ListNode min = null;
                int t=lists.length;//记录min下标
                for (int i = 0; i < lists.length; i++) {
                    if (lists[i] != null) {
                        if (min == null || min.val > lists[i].val) {
                            min = lists[i];
                            t = i;
                        }
                    }
                }
                if (min == null) {
                    return ans;
                } else if (ans == null) {
                    ans = min;
                    tail = ans;
                } else {
                    tail.next = min;
                    tail = min;
                }
                if (t < lists.length){
                    lists[t] = lists[t].next;
                }
            }
        }

        //使用队列优化比较 6ms 42.9 MB 居然比我快这么多
        public ListNode QueueErgeKLists(ListNode[] lists) {
            PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
            new PriorityQueue();
            for (ListNode node : lists) {
                if (node != null) {
                    pq.offer(node);
                }
            }
            ListNode head = new ListNode();
            ListNode tail = head;
            while(!pq.isEmpty()) {
                ListNode cur = pq.poll();
                tail.next = cur;
                tail = tail.next;
                if (cur.next != null) {
                    pq.offer(cur.next);
                }
            }
            return head.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
